Voir

Comparaison entre ancien et nouveau modèle[modifier | modifier le code]

Complexité en temps
Découvreur ou inventeur	Donald Shell (en)
Date de découverte	1959
Problèmes liés	Algorithme de tri, algorithme en place (en), tri par comparaison
Structure des données	Tableau
Pire cas
Moyenne
Meilleur cas
Pire cas

Complexité en temps
Découvreur ou inventeur	Donald Shell (en)
Date de découverte	1959
Problèmes liés	Algorithme de tri, algorithme en place (en), tri par comparaison
Structure des données	Tableau
Pire cas
Moyenne
Meilleur cas
Pire cas

Problème lié	Algorithme de tri
Structure des données	liste ou tableau

Tri de Shell[modifier | modifier le code]

ancien modèle[modifier | modifier le code]

nouveau modèle brouillon[modifier | modifier le code]

Brouillon!

nouveau modèle actuel[modifier | modifier le code]

Tri rapide[modifier | modifier le code]

ancien modèle[modifier | modifier le code]

Tri rapide

Quicksort en action sur une liste de nombre aléatoires. Les lignes horizontales sont les valeurs des pivots.

Problème lié	Algorithme de tri
Structure des données	liste ou tableau

nouveau modèle brouillon[modifier | modifier le code]

Brouillon!

Tri rapide

Quicksort en action sur une liste de nombres aléatoires. Les lignes horizontales sont les valeurs des pivots.

Découvreur ou inventeur	Charles Antony Richard Hoare^[4]
Date de découverte	1961^[4]
Problèmes liés	Tri par comparaison, diviser pour régner, algorithme de tri

Complexité en temps
Pire cas	$O(n^{2})$ ^[5]
Moyenne	$O(n\log n)$ ^[5]
Meilleur cas	$O(n\log n)$ ^[5]

Complexité en espace
Pire cas	$O(n)$
Moyenne	$O(\log n)$

nouveau modèle actuel[modifier | modifier le code]

Tri rapide

Quicksort en action sur une liste de nombres aléatoires. Les lignes horizontales sont les valeurs des pivots.

Découvreur ou inventeur	Charles Antony Richard Hoare^[4]
Date de découverte	1961^[4]
Problèmes liés	Tri par comparaison, diviser pour régner, algorithme de tri

Complexité en temps
Pire cas	$O(n^{2})$ ^[5]
Moyenne	$O(n\log n)$ ^[5]
Meilleur cas	$O(n\log n)$ ^[5]

Complexité en espace
Pire cas	$O(n)$
Moyenne	$O(\log n)$

Tri fusion[modifier | modifier le code]

ancien modèle[modifier | modifier le code]

Pas de modèle présent

nouveau modèle brouillon[modifier | modifier le code]

Brouillon!

Tri fusion

Animation du tri par fusion

Découvreur ou inventeur	John von Neumann
Date de découverte	1945
Problèmes liés	Tri par comparaison, tri stable (en)
Structures des données	Tableau, merge algorithm (en)
À l'origine de	Timsort

Complexité en temps
Pire cas	$O(n\log n)$
Moyenne	$O(n\log n)$
Meilleur cas	$O(n\log n)$

Complexité en espace
Pire cas	$O(n)$
Meilleur cas	$O(1)$ ^[6]

nouveau modèle actuel[modifier | modifier le code]

Tri fusion

Animation du tri par fusion

Découvreur ou inventeur	John von Neumann
Date de découverte	1945
Problèmes liés	Tri par comparaison, tri stable (en)
Structures des données	Tableau, merge algorithm (en)
À l'origine de	Timsort

Complexité en temps
Pire cas	$O(n\log n)$
Moyenne	$O(n\log n)$
Meilleur cas	$O(n\log n)$

Complexité en espace
Pire cas	$O(n)$
Meilleur cas	$O(1)$ ^[6]

Tri par tas[modifier | modifier le code]

ancien modèle[modifier | modifier le code]

Pas de modèle présent

nouveau modèle brouillon[modifier | modifier le code]

Brouillon!

Tri par tas

Une exécution de l'algorithme du tri par tas (Heapsort) trie une partie des valeurs permutées au hasard. Dans un premier temps, les éléments sont réarrangés pour respecter les conditions de tas. Avant le tri à proprement parler, la structure de l'arbre en tas est montrée brièvement par l'illustration.

Découvreur ou inventeur	J. W. J. Williams (en)
Date de découverte	1964
Problème lié	Algorithme de tri
Structure des données	Tableau
À l'origine de	Smoothsort

Complexité en temps
Pire cas	$O(n\log(n))$
Moyenne	$O(n\log(n))$
Meilleur cas	$O(n\log(n))$

Complexité en espace
Pire cas	$O(1)$

nouveau modèle actuel[modifier | modifier le code]

Tri par tas

Une exécution de l'algorithme du tri par tas (Heapsort) trie une partie des valeurs permutées au hasard. Dans un premier temps, les éléments sont réarrangés pour respecter les conditions de tas. Avant le tri à proprement parler, la structure de l'arbre en tas est montrée brièvement par l'illustration.

Découvreur ou inventeur	J. W. J. Williams (en)
Date de découverte	1964
Problème lié	Algorithme de tri
Structure des données	Tableau
À l'origine de	Smoothsort

Complexité en temps
Pire cas	$O(n\log(n))$
Moyenne	$O(n\log(n))$
Meilleur cas	$O(n\log(n))$

Complexité en espace
Pire cas	$O(1)$

Introsort[modifier | modifier le code]

Pas de modèle présent

ancien modèle[modifier | modifier le code]

nouveau modèle brouillon[modifier | modifier le code]

Brouillon!

Introsort

Découvreur ou inventeur	David Musser (en)^[7]
Date de découverte	1997
Problèmes liés	Algorithme de tri, hybrid algorithm (en)
Structure des données	Tableau

Complexité en temps
Pire cas	$O(n\log n)$
Moyenne	$O(n\log n)$

nouveau modèle actuel[modifier | modifier le code]

Introsort

Découvreur ou inventeur	David Musser (en)^[7]
Date de découverte	1997
Problèmes liés	Algorithme de tri, hybrid algorithm (en)
Structure des données	Tableau

Complexité en temps
Pire cas	$O(n\log n)$
Moyenne	$O(n\log n)$

Smoothsort[modifier | modifier le code]

Pas de modèle présent

ancien modèle[modifier | modifier le code]

nouveau modèle brouillon[modifier | modifier le code]

Brouillon!

Smoothsort

Smoothsort fonctionnant sur un réseau qui est presque en ordre. Les barres en haut montrent la structure de l'arbre.

Découvreur ou inventeur	Edsger Dijkstra
Date de découverte	1981
Problème lié	Algorithme de tri
Structure des données	Tableau
Basé sur	Tri par tas

Complexité en temps
Pire cas	$O(n\log n)$
Moyenne	$O(n\log n)$
Meilleur cas	$O(n)$

Complexité en espace
Pire cas	$O(n)$
Meilleur cas	$O(1)$

nouveau modèle actuel[modifier | modifier le code]

Smoothsort

Smoothsort fonctionnant sur un réseau qui est presque en ordre. Les barres en haut montrent la structure de l'arbre.

Découvreur ou inventeur	Edsger Dijkstra
Date de découverte	1981
Problème lié	Algorithme de tri
Structure des données	Tableau
Basé sur	Tri par tas

Complexité en temps
Pire cas	$O(n\log n)$
Moyenne	$O(n\log n)$
Meilleur cas	$O(n)$

Complexité en espace
Pire cas	$O(n)$
Meilleur cas	$O(1)$

Timsort[modifier | modifier le code]

ancien modèle[modifier | modifier le code]

Suaudeau/Bac à sable/test sur l'Infobox Algorithme Lua

Problème lié	Algorithme de tri
Structure des données	Tableau (informatique)

nouveau modèle brouillon[modifier | modifier le code]

Brouillon!

Timsort

Découvreur ou inventeur	Tim Peters (en)
Date de découverte	2002
Problèmes liés	Algorithme de tri, tri stable (en), tri par comparaison, hybrid algorithm (en), adaptive sort (en)
Structure des données	Tableau
Basé sur	Tri fusion, Tri par insertion

Complexité en temps
Pire cas	$O(n\log(n))$ ^[8]^,^[9]
Moyenne	$O(n\log(n))$
Meilleur cas	$O(n)$ ^[10]

Complexité en espace
Pire cas	$O(n)$

nouveau modèle actuel[modifier | modifier le code]

Timsort

Découvreur ou inventeur	Tim Peters (en)
Date de découverte	2002
Problèmes liés	Algorithme de tri, tri stable (en), tri par comparaison, hybrid algorithm (en), adaptive sort (en)
Structure des données	Tableau
Basé sur	Tri fusion, Tri par insertion

Complexité en temps
Pire cas	$O(n\log(n))$ ^[8]^,^[9]
Moyenne	$O(n\log(n))$
Meilleur cas	$O(n)$ ^[10]

Complexité en espace
Pire cas	$O(n)$

Tri arborescent[modifier | modifier le code]

ancien modèle[modifier | modifier le code]

Pas de modèle présent

nouveau modèle brouillon[modifier | modifier le code]

Brouillon!

Tri arborescent

Problème lié	Algorithme de tri
Structures des données	Tableau, arbre binaire

Complexité en temps
Pire cas	$O(n^{2})$
Moyenne	$O(n\log(n))$
Meilleur cas	$O(n\log(n))$

Complexité en espace
Pire cas	$O(n)$

nouveau modèle actuel[modifier | modifier le code]

Tri arborescent

Problème lié	Algorithme de tri
Structures des données	Tableau, arbre binaire

Complexité en temps
Pire cas	$O(n^{2})$
Moyenne	$O(n\log(n))$
Meilleur cas	$O(n\log(n))$

Complexité en espace
Pire cas	$O(n)$

Tri à peigne[modifier | modifier le code]

ancien modèle[modifier | modifier le code]

Tri à peigne

Exemple de tri d'une liste de nombres par le tri à peigne.

Problème lié	Algorithme de tri
Structure des données	liste ou tableau

nouveau modèle brouillon[modifier | modifier le code]

Brouillon!

Tri à peigne

Exemple de tri d'une liste de nombres par le tri à peigne.

Problème lié	Algorithme de tri
Structure des données	Tableau

Complexité en temps
Pire cas	$O(n^{2})$ ^[11]
Meilleur cas	$O(n\log n)$

Complexité en espace
Pire cas	$O(1)$

nouveau modèle actuel[modifier | modifier le code]

Tri à peigne

Exemple de tri d'une liste de nombres par le tri à peigne.

Problème lié	Algorithme de tri
Structure des données	Tableau

Complexité en temps
Pire cas	$O(n^{2})$ ^[11]
Meilleur cas	$O(n\log n)$

Complexité en espace
Pire cas	$O(1)$

Tri à bulles[modifier | modifier le code]

ancien modèle[modifier | modifier le code]

Pas de modèle présent

nouveau modèle brouillon[modifier | modifier le code]

Brouillon!

Tri à bulles

Tableau de nombres représenté en 2 dimensions : en abscisse la position du nombre dans le tableau, en ordonnée la valeur du nombre. On voit qu'avec le tri à bulles, les grands nombres trouvent leur position finale avant les petits.

Problèmes liés	Algorithme de tri, tri stable (en), tri par comparaison
Structure des données	Tableau

Complexité en temps
Pire cas	$O(n^{2})$
Moyenne	$O(n^{2})$
Meilleur cas	$O(n)$

Complexité en espace
Pire cas	$O(1)auxiliary$

nouveau modèle actuel[modifier | modifier le code]

Tri à bulles

Tableau de nombres représenté en 2 dimensions : en abscisse la position du nombre dans le tableau, en ordonnée la valeur du nombre. On voit qu'avec le tri à bulles, les grands nombres trouvent leur position finale avant les petits.

Problèmes liés	Algorithme de tri, tri stable (en), tri par comparaison
Structure des données	Tableau

Complexité en temps
Pire cas	$O(n^{2})$
Moyenne	$O(n^{2})$
Meilleur cas	$O(n)$

Complexité en espace
Pire cas	$O(1)auxiliary$

Tri par insertion[modifier | modifier le code]

ancien modèle[modifier | modifier le code]

Tri par insertion

Exemple du tri par insertion utilisant une liste de nombres aléatoires

Problème lié	Algorithme de tri
Structure des données	liste ou tableau

nouveau modèle brouillon[modifier | modifier le code]

Brouillon!

Tri par insertion

Exemple du tri par insertion utilisant une liste de nombres aléatoires

Problèmes liés	Algorithme de tri, tri stable (en), tri par comparaison, adaptive sort (en), algorithme en place (en), algorithme en ligne
Structure des données	Tableau
À l'origine de	Timsort

Complexité en temps
Pire cas	$O(n^{2})$
Moyenne	$O(n^{2})$
Meilleur cas	$O(n)$

Complexité en espace
Pire cas	$O(1)$

nouveau modèle actuel[modifier | modifier le code]

Tri par insertion

Exemple du tri par insertion utilisant une liste de nombres aléatoires

Problèmes liés	Algorithme de tri, tri stable (en), tri par comparaison, adaptive sort (en), algorithme en place (en), algorithme en ligne
Structure des données	Tableau
À l'origine de	Timsort

Complexité en temps
Pire cas	$O(n^{2})$
Moyenne	$O(n^{2})$
Meilleur cas	$O(n)$

Complexité en espace
Pire cas	$O(1)$

Tri par sélection[modifier | modifier le code]

ancien modèle[modifier | modifier le code]

Tri par sélection

Exemple du tri par sélection utilisant une liste de nombres aléatoires

Problème lié	Algorithme de tri
Structure des données	liste ou tableau

nouveau modèle brouillon[modifier | modifier le code]

Brouillon!

Tri par sélection

Exemple du tri par sélection utilisant une liste de nombres aléatoires

Problème lié	Algorithme de tri
Structure des données	Tableau

Complexité en temps
Pire cas	$O(n^{6})$
Moyenne	$O(n^{2})$
Meilleur cas	$O(n^{2}75)$

Complexité en espace
Pire cas	$O(1)$

nouveau modèle actuel[modifier | modifier le code]

Tri par sélection

Exemple du tri par sélection utilisant une liste de nombres aléatoires

Problème lié	Algorithme de tri
Structure des données	Tableau

Complexité en temps
Pire cas	$O(n^{6})$
Moyenne	$O(n^{2})$
Meilleur cas	$O(n^{2}75)$

Complexité en espace
Pire cas	$O(1)$

Tri cocktail[modifier | modifier le code]

ancien modèle[modifier | modifier le code]

Pas de modèle présent

nouveau modèle brouillon[modifier | modifier le code]

Brouillon!

Tri cocktail

Problèmes liés	Algorithme de tri, tri stable (en)
Structure des données	Tableau
Basé sur	Tri à bulles

Complexité en temps
Pire cas	$O(n^{2})$
Moyenne	$O(n^{2})$
Meilleur cas	$O(n)$

Complexité en espace
Pire cas	$O(1)$

nouveau modèle actuel[modifier | modifier le code]

Tri cocktail

Problèmes liés	Algorithme de tri, tri stable (en)
Structure des données	Tableau
Basé sur	Tri à bulles

Complexité en temps
Pire cas	$O(n^{2})$
Moyenne	$O(n^{2})$
Meilleur cas	$O(n)$

Complexité en espace
Pire cas	$O(1)$

Tri stupide[modifier | modifier le code]

ancien modèle[modifier | modifier le code]

Tri stupide

Avec le tri stupide, un seul mélange peut suffire pour trier les éléments. Cette probabilité est cependant très faible.

Problème lié	Algorithme de tri
Structure des données	Liste ou tableau

nouveau modèle brouillon[modifier | modifier le code]

Brouillon!

Tri stupide

Avec le tri stupide, un seul mélange peut suffire pour trier les éléments. Cette probabilité est cependant très faible.

Problèmes liés	Algorithme de tri, Algorithme de Las Vegas
Structure des données	Tableau

Complexité en temps
Pire cas	$\infty$ ^[12]
Moyenne	$O((n+1)!)$ ^[12]
Meilleur cas	$O(n)$ ^[12]

Complexité en espace
Pire cas	$O(n)$ ^[12]

nouveau modèle actuel[modifier | modifier le code]

Tri stupide

Avec le tri stupide, un seul mélange peut suffire pour trier les éléments. Cette probabilité est cependant très faible.

Problèmes liés	Algorithme de tri, Algorithme de Las Vegas
Structure des données	Tableau

Complexité en temps
Pire cas	$\infty$ ^[12]
Moyenne	$O((n+1)!)$ ^[12]
Meilleur cas	$O(n)$ ^[12]

Complexité en espace
Pire cas	$O(n)$ ^[12]

Tri faire-valoir[modifier | modifier le code]

ancien modèle[modifier | modifier le code]

Tri faire-valoir

Visualisation du tri faire-valoir (qui ne montre que les échanges).

Problème lié	Algorithme de tri
Structure des données	liste ou tableau

nouveau modèle brouillon[modifier | modifier le code]

Brouillon!

Tri faire-valoir

Visualisation du tri faire-valoir (qui ne montre que les échanges).

Problème lié	Algorithme de tri
Structure des données	Tableau

Complexité en temps
Pire cas	$O(n^{log{3}/log{1.5}})$

Complexité en espace
Pire cas	$O(n)$

nouveau modèle actuel[modifier | modifier le code]

Tri faire-valoir

Visualisation du tri faire-valoir (qui ne montre que les échanges).

Problème lié	Algorithme de tri
Structure des données	Tableau

Complexité en temps
Pire cas	$O(n^{log{3}/log{1.5}})$

Complexité en espace
Pire cas	$O(n)$

Tri comptage[modifier | modifier le code]

ancien modèle[modifier | modifier le code]

Pas de modèle présent

nouveau modèle brouillon[modifier | modifier le code]

Brouillon!

Tri comptage

Problème lié	Algorithme de tri
Structure des données	Tableau

Complexité en temps
Pire cas	$O(n+k)$

Complexité en espace
Pire cas	$O(n+k)$

nouveau modèle actuel[modifier | modifier le code]

Tri comptage

Problème lié	Algorithme de tri
Structure des données	Tableau

Complexité en temps
Pire cas	$O(n+k)$

Complexité en espace
Pire cas	$O(n+k)$

Tri par base[modifier | modifier le code]

ancien modèle[modifier | modifier le code]

Pas de modèle présent

nouveau modèle brouillon[modifier | modifier le code]

Brouillon!

Tri par base

Découvreur ou inventeur	Herman Hollerith
Date de découverte	1887
Problème lié	Algorithme de tri
Structure des données	Tableau

Complexité en temps
Pire cas	$O(w\cdot n)$

Complexité en espace
Pire cas	$O(w.n)$

nouveau modèle actuel[modifier | modifier le code]

Tri par base

Découvreur ou inventeur	Herman Hollerith
Date de découverte	1887
Problème lié	Algorithme de tri
Structure des données	Tableau

Complexité en temps
Pire cas	$O(w\cdot n)$

Complexité en espace
Pire cas	$O(w.n)$

Tri par paquets[modifier | modifier le code]

ancien modèle[modifier | modifier le code]

Pas de modèle présent

nouveau modèle brouillon[modifier | modifier le code]

Brouillon!

Tri par paquets

Problèmes liés	Algorithme, algorithme de tri
Structure des données	Tableau
Basé sur	Pigeonhole sort (en)

Complexité en temps
Pire cas	$O(n^{2})$

Complexité en espace
Pire cas	$O(n\cdot k)$
Moyenne	$O(n+{\frac {n^{2}}{k}}+k)$

nouveau modèle actuel[modifier | modifier le code]

Tri par paquets

Problèmes liés	Algorithme, algorithme de tri
Structure des données	Tableau
Basé sur	Pigeonhole sort (en)

Complexité en temps
Pire cas	$O(n^{2})$

Complexité en espace
Pire cas	$O(n\cdot k)$
Moyenne	$O(n+{\frac {n^{2}}{k}}+k)$

Tri bitonique[modifier | modifier le code]

ancien modèle[modifier | modifier le code]

Tri bitonique

Réseau de tri bitonique à huit entrées ; 24 comparateurs, profondeur 6.

Problème lié	Algorithme de tri

nouveau modèle brouillon[modifier | modifier le code]

Brouillon!

Tri bitonique

Réseau de tri bitonique à huit entrées ; 24 comparateurs, profondeur 6.

Découvreur ou inventeur	Ken Batcher
Date de découverte	1968
Problèmes liés	Parallel algorithm (en), algorithme de tri
Structure des données	Tableau

Complexité en temps
Pire cas	$O(\log ^{2}(n))$
Moyenne	$O(\log ^{2}(n))$
Meilleur cas	$O(\log ^{2}(n))$

Complexité en espace
Pire cas	$O(n\log ^{2}(n))$

nouveau modèle actuel[modifier | modifier le code]

Tri bitonique

Réseau de tri bitonique à huit entrées ; 24 comparateurs, profondeur 6.

Découvreur ou inventeur	Ken Batcher
Date de découverte	1968
Problèmes liés	Parallel algorithm (en), algorithme de tri
Structure des données	Tableau

Complexité en temps
Pire cas	$O(\log ^{2}(n))$
Moyenne	$O(\log ^{2}(n))$
Meilleur cas	$O(\log ^{2}(n))$

Complexité en espace
Pire cas	$O(n\log ^{2}(n))$

Tri pair-impair[modifier | modifier le code]

ancien modèle[modifier | modifier le code]

Tri pair-impair par transposition

Exemple de tri d'une liste de nombres par le tri pair-impair.

Problème lié	Algorithme de tri
Structure des données	liste ou tableau

nouveau modèle brouillon[modifier | modifier le code]

Brouillon!

Tri pair-impair

Exemple de tri d'une liste de nombres par le tri pair-impair.

Découvreur ou inventeur	Nico Habermann (en)
Date de découverte	1972
Problème lié	Algorithme de tri
Structure des données	Tableau

Complexité en temps
Pire cas	$O(n^{2})$
Meilleur cas	$O(n)$

Complexité en espace
Pire cas	$O(1)$

nouveau modèle actuel[modifier | modifier le code]

Tri pair-impair

Exemple de tri d'une liste de nombres par le tri pair-impair.

Découvreur ou inventeur	Nico Habermann (en)
Date de découverte	1972
Problème lié	Algorithme de tri
Structure des données	Tableau

Complexité en temps
Pire cas	$O(n^{2})$
Meilleur cas	$O(n)$

Complexité en espace
Pire cas	$O(1)$

Tri de crêpes[modifier | modifier le code]

ancien modèle[modifier | modifier le code]

Pas de modèle présent

nouveau modèle brouillon[modifier | modifier le code]

Brouillon!

Tri de crêpes

Rotation d'une partie de la pile de crêpes à l'aide de la spatule.

Problème lié	Algorithme de tri

nouveau modèle actuel[modifier | modifier le code]

Tri de crêpes

Rotation d'une partie de la pile de crêpes à l'aide de la spatule.

Problème lié	Algorithme de tri

Recherche dichotomique[modifier | modifier le code]

ancien modèle[modifier | modifier le code]

Pas de modèle présent

nouveau modèle brouillon[modifier | modifier le code]

Brouillon!

Dichotomie

Problèmes liés	Algorithme de recherche, diviser pour régner
Structure des données	Tableau

nouveau modèle actuel[modifier | modifier le code]

Dichotomie

Problèmes liés	Algorithme de recherche, diviser pour régner
Structure des données	Tableau

exemple[modifier | modifier le code]

ancien modèle[modifier | modifier le code]

nouveau modèle brouillon[modifier | modifier le code]

nouveau modèle actuel[modifier | modifier le code]

↑ ^{a et b} (en) D. L. Shell, « A high-speed sorting procedure », Communications of the ACM, New York, ACM, vol. 2, n^o 7,‎ 1^er juillet 1959, p. 30-32 (ISSN 0001-0782 et 1557-7317, OCLC 1514517, DOI 10.1145/368370.368387)
↑ ^{a et b} Vaughan Pratt (en), « Shellsort and Sorting Networks (Outstanding Dissertations in the Computer Sciences) »
↑ ^{a b c d e et f} « https://www.cs.wcupa.edu/rkline/ds/shell-comparison.html »
↑ ^{a b c et d} (en) C. A. R. Hoare, « Algorithm 64: Quicksort », Communications of the ACM, New York, ACM, vol. 4, n^o 7,‎ 1^er juillet 1961, p. 321 (ISSN 0001-0782 et 1557-7317, OCLC 1514517, DOI 10.1145/366622.366644)
↑ ^{a b c d e et f} « https://www.khanacademy.org/computing/computer-science/algorithms/quick-sort/a/analysis-of-quicksort » (consulté le 9 mars 2017)
↑ ^{a et b} Steven Skiena, The Algorithm Design Manual, Springer Science+Business Media, 2008, 730 p. (ISBN 978-1-84800-069-8), p. 122
↑ ^{a et b} (en) David R. Musser, « Introspective Sorting and Selection Algorithms », Software: Practice and Experience, Wiley-Blackwell, vol. 27, n^o 8,‎ 1997, p. 983-993 (ISSN 1097-024X et 0038-0644, DOI 10.1002/(SICI)1097-024X(200005)30:6<617::AID-SPE311>3.0.CO;2-A)
↑ ^{a et b} Tim Peters (d), « http://mail.python.org/pipermail/python-dev/2002-July/026837.html », 24 février 2011 : « [Timsort] also has good aspects: It's stable (items that compare equal retain their relative order, so, e.g., if you sort first on zip code, and a second time on name, people with the same name still appear in order of increasing zip code; this is important in apps that, e.g., refine the results of queries based on user input). ... It has no bad cases (O(N log N) is worst case; N−1 compares is best). »
↑ ^{a et b} « http://drops.dagstuhl.de/opus/volltexte/2018/9467/ » : « TimSort is an intriguing sorting algorithm designed in 2002 for Python, whose worst-case complexity was announced, but not proved until our recent preprint. »
↑ ^{a et b} (en) Badrish Chandramouli et Jonathan Goldstein, « Patience is a virtue: revisiting merge and sort on modern processors », SIGMOD conference,‎ 1^er juin 2014, p. 731-742 (DOI 10.1145/2588555.2593662)
↑ ^{a et b} (en) Bronislava Brejová, « Analyzing variants of Shellsort », Information Processing Letters, Elsevier, vol. 79, n^o 5,‎ septembre 2001, p. 223-227 (ISSN 0020-0190 et 1872-6119, OCLC 38995181, DOI 10.1016/S0020-0190(00)00223-4)
↑ ^{a b c d e f g et h} (en) Hermann Gruber, Markus Holzer et Oliver Ruepp, « Sorting the Slow Way: An Analysis of Perversely Awful Randomized Sorting Algorithms », Fun with Algorithms: 4th International Conference, FUN 2007, Castiglioncello, Italy, June 3-5, 2007. Proceedings, Springer Science+Business Media,‎ 2007, p. 183-197 (ISBN 978-3-540-72913-6 et 978-3-540-72914-3, DOI 10.1007/978-3-540-72914-3_17)

[wikidata-b7ae7a7232e94dfab7f66aa545d87ddcddaca362Q55880809-1] {a et b} (en) D. L. Shell, « A high-speed sorting procedure », Communications of the ACM, New York, ACM, vol. 2, n^o 7,‎ 1^er juillet 1959, p. 30-32 (ISSN 0001-0782 et 1557-7317, OCLC 1514517, DOI 10.1145/368370.368387)

[wikidata-06f2e0c1a7950163e27c386af2f760e6f28c67fc-2] {a et b} Vaughan Pratt (en), « Shellsort and Sorting Networks (Outstanding Dissertations in the Computer Sciences) »

[wikidata-b0e7c1ec94843509cf8f09316610b0022dc9348f-3] {a b c d e et f} « https://www.cs.wcupa.edu/rkline/ds/shell-comparison.html »

[wikidata-902700ebb24fee7097cfa0aa877efab199ae4eb4Q55952563-4] {a b c et d} (en) C. A. R. Hoare, « Algorithm 64: Quicksort », Communications of the ACM, New York, ACM, vol. 4, n^o 7,‎ 1^er juillet 1961, p. 321 (ISSN 0001-0782 et 1557-7317, OCLC 1514517, DOI 10.1145/366622.366644)

[wikidata-6ba7c77af82618ecac179a5d4db7f8c913cda63c-5] {a b c d e et f} « https://www.khanacademy.org/computing/computer-science/algorithms/quick-sort/a/analysis-of-quicksort » (consulté le 9 mars 2017)

[wikidata-04e6cdb4df70c42ec53c099b847b50962c418ac5Q93743409-6] {a et b} Steven Skiena, The Algorithm Design Manual, Springer Science+Business Media, 2008, 730 p. (ISBN 978-1-84800-069-8), p. 122

[wikidata-0de17efca6a7ebea2722f0ce3b862abda2909c1cQ93757177-7] {a et b} (en) David R. Musser, « Introspective Sorting and Selection Algorithms », Software: Practice and Experience, Wiley-Blackwell, vol. 27, n^o 8,‎ 1997, p. 983-993 (ISSN 1097-024X et 0038-0644, DOI 10.1002/(SICI)1097-024X(200005)30:6<617::AID-SPE311>3.0.CO;2-A)

[wikidata-e49864ca6eccdb9786cd6469750ece5cb8a7ca27-8] {a et b} Tim Peters (d), « http://mail.python.org/pipermail/python-dev/2002-July/026837.html », 24 février 2011 : « [Timsort] also has good aspects: It's stable (items that compare equal retain their relative order, so, e.g., if you sort first on zip code, and a second time on name, people with the same name still appear in order of increasing zip code; this is important in apps that, e.g., refine the results of queries based on user input). ... It has no bad cases (O(N log N) is worst case; N−1 compares is best). »

[wikidata-c5a250f1e6c7bc20377926e554ea8864c243aa25-9] {a et b} « http://drops.dagstuhl.de/opus/volltexte/2018/9467/ » : « TimSort is an intriguing sorting algorithm designed in 2002 for Python, whose worst-case complexity was announced, but not proved until our recent preprint. »

[wikidata-5946c04a3d0875fb4ec1c9ddc9c7079b6d860f9cQ93858163-10] {a et b} (en) Badrish Chandramouli et Jonathan Goldstein, « Patience is a virtue: revisiting merge and sort on modern processors », SIGMOD conference,‎ 1^er juin 2014, p. 731-742 (DOI 10.1145/2588555.2593662)

[wikidata-1bba0e2bd801faa04a5564eaa13856428aa95974Q55885385-11] {a et b} (en) Bronislava Brejová, « Analyzing variants of Shellsort », Information Processing Letters, Elsevier, vol. 79, n^o 5,‎ septembre 2001, p. 223-227 (ISSN 0020-0190 et 1872-6119, OCLC 38995181, DOI 10.1016/S0020-0190(00)00223-4)

[wikidata-896ef3a29f7fea5b1f42c7af4e1564caf0aa8e93Q56115129-12] {a b c d e f g et h} (en) Hermann Gruber, Markus Holzer et Oliver Ruepp, « Sorting the Slow Way: An Analysis of Perversely Awful Randomized Sorting Algorithms », Fun with Algorithms: 4th International Conference, FUN 2007, Castiglioncello, Italy, June 3-5, 2007. Proceedings, Springer Science+Business Media,‎ 2007, p. 183-197 (ISBN 978-3-540-72913-6 et 978-3-540-72914-3, DOI 10.1007/978-3-540-72914-3_17)

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]